Section: New Results

Quantum Information

Participants : Xavier Bonnetain, Rémi Bricout, Kaushik Chakraborty, André Chailloux, Shouvik Ghorai, Antoine Grospellier, Anirudh Krishna, Gaëtan Leurent, Anthony Leverrier, Vivien Londe, María Naya Plasencia, Andrea Olivo, Jean-Pierre Tillich, Sristy Agrawal, André Schrottenloher.

Our research in quantum information focusses on several axes: quantum codes with the goal of developing better error correction strategies to build large quantum computers, quantum cryptography which exploits the laws of quantum mechanics to derive security guarantees, relativistic cryptography which exploits in addition the fact that no information can travel faster than the speed of light and finally quantum cryptanalysis which investigates how quantum computers could be harnessed to attack classical cryptosystems.

Quantum codes

Protecting quantum information from external noise is an issue of paramount importance for building a quantum computer. It also worthwhile to notice that all quantum error-correcting code schemes proposed up to now suffer from the very same problem that the first (classical) error-correcting codes had: there are constructions of good quantum codes, but for the best of them it is not known how to decode them in polynomial time.

Recent results:

• Decoding algorithm for quantum expander codes [72], [57], [58], [59], [73], [35]. In this work, A. Grospellier, A. Leverrier and O. Fawzi analyze an efficient decoding algorithm for quantum expander codes and prove that it suppresses errors exponentially in the local stochastic noise model. As an application, this shows that this family of codes can be used to obtain quantum fault-tolerance with only a constant overhead in terms of qubits, compared to a polylogarithmic overhead as in previous schemes. This is a crucial step in order to eventually build large universal quantum computers.

• Construction of quantum LDPC codes from regular tessellations of hyperbolic 4-space [64], [62]. In this work, V. Londe proposes a variant of a construction of Guth and Lubotzky that yields a family of constant rate codes with a polynomial minimum distance. The main interest of this construction is that is is based on a regular tessellation of hyperbolic 4-space by hypercubes. This nice local structure is exploited to design and analyze an efficient decoding algorithm that corrects arbitrary errors of weight logarithmic in the code length.

• Construction of quantum codes based on the real projective space [63]. In this work, V. Londe studies a family of almost LDPC codes with a large minimum distance and another efficient decoding algorithm.

• We were also awarded a European Quantera project “QCDA” to investigate and develop better quantum error-correcting codes and schemes for fault-tolerance.

Quantum cryptography

Quantum cryptography exploits the laws of quantum physics to establish the security of certain cryptographic primitives. The most studied one is certainly quantum key distribution, which allows two distant parties to establish a secret using an untrusted quantum channel. Our activity in this field is particularly focussed on protocols with continuous variables, which are well-suited to implementations. Another primitive is quantum money and was in fact the first proposed idea of quantum cryptography in the 70s. However, this primitive hasn't received much attention because its implementation requires quantum memories, which weren't available until now.

Recent results:

• Full security proof for BB84 [27]. In this work A. Leverrier, with M. Tomamichel, give a detailed and self-contained security proof for BB84, the most studied quantum key distribution protocol. Many simplified proofs appear in the literature, but are usually incomplete and fail to address the whole protocol.

• Security proof of continuous-variable quantum key distribution [26], [36], [37]. In this work, A. Leverrier establishes for the first time a security reduction from general attacks to a class of simple attacks called “collective Gaussian” attacks. This result exploits in a crucial way a recent Gaussian de Finetti theorem that applies to quantum systems of infinite dimension [75], [61], [34].

• In [22], A. Chailloux and I. Kerenidis present an extended version on results for optimal quantum bit commitment and coin flipping. Those results show what is the best way to quantumly perform those protocols in the information-theoretic setting. In the extended version, we also show that the bound for quantum bit commitment cannot be achieved classically, even with an access to an ideal coin flipping primitive.

• We were also awarded an ANR project quBIC and an “Émergence” project from Ville de Paris to study quantum money schemes in collaboration with UPMC, LKB and IRIF.

Relativistic cryptography

Two-party cryptographic tasks are well-known to be impossible without complexity assumptions, either in the classical or the quantum world. Remarkably, such no-go theorems become invalid when adding the physical assumption that no information can travel faster than the speed of light. This additional assumption gives rise to the emerging field of relativistic cryptography. We worked on this topic for several years and Andrea Olivo was recruited as a PhD student to continue working on both theoretical and practical aspects of relativistic cryptography.

Recent results:

• Relativistic zero-knowledge: In [46], A. Chailloux and A. Leverrier construct a relativistic zero-knowledge protocol for any $NP$ complete problem. The main technical tool is the analysis of quantum consecutive measurements, which allows us to prove security against quantum adversaries. While this technique is applied to the relativistic setting, it also has implications for more standard quantum cryptography.

• In [16], R. Bricout and A. Chailloux study relativistic multi-round bit commitment schemes. They show optimal classical cheating strategies for the canonical $F_Q$ commitment scheme. This shows that the security proof derived last year on the relativistic $F_Q$ commitment scheme is essentially optimal against classical adversaries.

Quantum cryptanalysis of symmetric primitives

Symmetric cryptography seems at first sight much less affected in the post-quantum world than asymmetric cryptography: its main known threat seemed for a long time Grover's algorithm, which allows for an exhaustive key search in the square root of the normal complexity. For this reason, it was usually believed that doubling key lengths suffices to maintain an equivalent security in the post-quantum world. However, a lot of work is certainly required in the field of symmetric cryptography in order to “quantize” the classical families of attacks in an optimized way, as well as to find new dedicated quantum attacks. M. Naya Plasencia has recently been awarded an ERC Starting grant for her project named QUASYModo on this topic, that has started on september 2017.

Recent results:

• In a result published in Asiacrypt 2017 [47] and done during the internship of André Schrottenloher [76] a new quantum algorithm for finding collisions is proposed. The algorithm is based on BHT and exploits distinguished points as well as an improved optimization of the parameters, and allows to find, for the first time, collisions on $n$ bits with a better time complexity than $2^{n/2}$ while needing a polynomial amount of quantum memory.

• Two of the most popular symmetric cryptanalysis families are differential and linear cryptanalysis. In [60] (also presented in [33]), G. Leurent, M. Kaplan, A. Leverrier and M. Naya-Plasencia have proposed efficient ways of quantizing these attacks in different models, obtaining some non-intuitive results: just quantizing the best classical attack does not always provide the best quantum attack.

• X. Bonnetain and M. Naya-Plasencia have obtained some new results, preliminarily described in [14] and presented at [38], that consider the tweak proposed at Eurocrypt this year of using modular additions to counter Simon's attacks. They have studied the best attacks on these constructions, that use Kuperberg's algorithm. They have also simulated the cost of such attacks, improved the algorithm, applied this to a widely-used construction and to some slide attacks, and finally dimensionated the symmetric construction in order to stay secure to these attacks. They have concluded that the proposed tweak does not seam realistic.

• In [44], an attack on the superposition model of the CAESAR cadidate AEZ is proposed, showing that this construction would be completely broken in that scenario.